#include <vector>
#include <optional>
#include <functional>
#include <stdexcept>
#include <random>
#include <iostream>
#include <utility> 
#include <string.h>
#include <bitset>
#include <string>
#include <fstream>
#include <cstring> 
#include <array>

using Byte16=std::array<uint8_t,16>;

struct bins
{
    Byte16 content; //原始值
    int position;//原始位置
    int state;//状态 0,1,2: hash1,hash2,hash3 ,3:stash
};

class CuckooHash3{
public:
    explicit CuckooHash3(size_t NUM, float alpha = 0.5, size_t maxKicks = 500): 
        NUM(NUM),N(NUM/(3*alpha)+1), maxKicks(maxKicks),
        tables{std::vector<std::optional<bins>>(N),
               std::vector<std::optional<bins>>(N),
               std::vector<std::optional<bins>>(N)},
        stash{std::nullopt, std::nullopt, std::nullopt,std::nullopt},
        rng(std::random_device{}()){
                salts[0]  = 0x3F9A2C8D7E1B4A6F;
                salts[1]  = 0x8D3F2E1A9C7B4D5E;
                salts[2]  = 0x5A7C9D3F8B2E1A6D;
    }

    bool find(const Byte16& x) const {
        // 三表查找 + stash
        for (int i = 0; i < 3; i++) {
            size_t idx = hash(x, i);
            if (tables[i][idx] && (*tables[i][idx]).content==x) return true;
        }

        for(int i=0;i<3;i++)//第四个桶用不上
        {
            if(stash[i] && (*stash[i]).content==x) return true;
        }

        return false;
    }

    void insert(const bins& x) {
        if (find(x.content)) return;
        auto cur = x;
        for (size_t kick = 0; kick < maxKicks; kick++) {
            for (int i = 0; i < 3; i++) {
                size_t idx = hash(cur.content, i);
                if (!tables[i][idx]) {
                    cur.state = i;//确认hash函数
                    tables[i][idx] = cur;
                    return;
                }
            }
            // 三处都满，随机选择一处踢出
            int i = std::uniform_int_distribution<int>(0,2)(rng);
            size_t idx = hash(cur.content, i);
            cur.state = i;//选择该位置
            std::swap(cur, *tables[i][idx]);
        }
        cur.state = 3;//到桶内
        // 踢出次数过多，放入 stash
        for(int i=0;i< 3;i++){
            if(!stash[i]){
                stash[i] = cur;
                return;
            }
        }      
        stash[3] = cur; 
        rehash();  // stash 已满则重哈希
    }
    
    size_t get_N(){
       return N*3; 
    }
        // 提供一个公共成员函数，返回 tables 的引用
    const std::vector<std::optional<bins>>& getTable(int index) const {
        if (index < 3) {
            return tables[index];
        }
        throw std::out_of_range("Index out of range");
    }
    const std::array<std::optional<bins>, 4>& getStash() const{
        return this->stash;
    }

public:
    std::mt19937 rng;//随机种子
private:
    size_t NUM;//总元素个数
    float alpha; //负载因子本次取0.5
    size_t N, maxKicks;//需要单个hash表的元素个数，最大尝试次数
    std::vector<std::optional<bins>> tables[3];//三个hash表
    std::array<std::optional<bins>, 4> stash;//3个桶一个备用
    uint64_t salts[3];// 用于hash计算的值
  

    size_t hash(const Byte16& arr, int i) const {
            uint64_t part1 = 0;
            uint64_t part2 = 0;
            for (size_t i = 0; i < 8; ++i) {
                part1 = (part1 << 8) | arr[i];
                part2 = (part2 << 8) | arr[i + 8];
            }
            std::hash<uint64_t> hasher;
            return (hasher(part1) ^ (hasher(part2) << 1)^salts[i])%N;
    }
    
    void rehash() {
        // 扩容并重插所有元素（主表 + stash）
        size_t oldN = N;
        N *= 2;
        std::vector<std::optional<bins>> old0 = std::move(tables[0]);
        std::vector<std::optional<bins>> old1 = std::move(tables[1]);
        std::vector<std::optional<bins>> old2 = std::move(tables[2]);
        tables[0].assign(N, std::nullopt);
        tables[1].assign(N, std::nullopt);
        tables[2].assign(N, std::nullopt);
        std::array<std::optional<bins>, 4> oldStash;
        for(int i=0;i<4;i++){
            oldStash[i] = stash[i];
            stash[i].reset();
        }
        
        

        for (auto& tbl : {&old0, &old1, &old2}) {
            for (auto& o : *tbl) {
                if (o) insert(*o);
            }
        }
        
        for(int i=0;i<4;i++){
            if(oldStash[i])insert(*oldStash[i]);
        }
    }
};

int main(int argc, char* argv[]){
        
    if (argc != 4) {
        std::cerr << "Usage: " << argv[0] << " <file_path>" << std::endl;
    return 1;
    }
    //获取文件名
    std::string file_path = argv[1];
    //获取结果存放处
    std::string output_path = argv[2];//hash标记+值
    std::string posioton_path = argv[3];//位表，用于还原
  
    // 打开文件
    std::ifstream file(file_path, std::ios::binary);
    if (!file) {
        std::cerr << "Error opening file: " << file_path << std::endl;
        return 1;
    }
    
    // 获取文件大小
    file.seekg(0, std::ios::end);
    size_t file_size = file.tellg();
    file.seekg(0, std::ios::beg);

    // 每个128位数占16字节
    const int bit_size = 128 / 8;  // 16 字节
    size_t num_elements = file_size / bit_size;  // 计算128位数的数量
    
     // 如果文件大小不适合包含完整的128位数，输出错误
    if (file_size % bit_size != 0) {
        std::cerr << "Warning: File size is not a multiple of 128 bits." << std::endl;
        return 1;
    }
    
    CuckooHash3 cuckoo(num_elements);
    

    int count = 1;
    Byte16 buffer;
    while (file.read(reinterpret_cast<char*>(buffer.data()), buffer.size())) {
        // 处理 buffer
         cuckoo.insert({buffer,count,4}); //4代表虚拟值
         count++;
    }
    std::ofstream file_out(output_path, std::ios::binary);
    std::ofstream postion_out(posioton_path,std::ios::binary);
    if (!file_out.is_open()||!postion_out.is_open()) {
        std::cerr << "文件打开失败!" << std::endl;
        return 1;
    }
    //布谷鸟文件存入的是多个32+128的原始位置信息和值，
    char zerobit[16]; 
    std::memset(zerobit, 0, sizeof(zerobit)); // 全部设为 0
    int mark = 4;
    int pos = 0;
    unsigned char bytes[16];
  
    for(int i=0;i<3;i++){
        auto table = cuckoo.getTable(i);
        for(auto& x : table){
            if(x){
                
                auto node = *x;
                pos = node.position;
                // 写入 32 位的 hash标记 0,1,2,3
                int value = node.state;//hash标记
                file_out.write(reinterpret_cast<char*>(&value), 4);
                // 写入128位的数值
                file_out.write(reinterpret_cast<char*>(node.content.data()), 16);
            }else{
             
                pos = 0;
                //写入虚拟值标记
                file_out.write(reinterpret_cast<char*>(&mark), 4);
                //写入0bit串
                file_out.write(zerobit,16);
               
            }
            postion_out.write(reinterpret_cast<char*>(&pos), sizeof(pos));//写入位置，0表示虚拟值
        }
    }
    auto& stash = cuckoo.getStash();
     
    for(int i=0;i<3;i++){
        if(stash[i]){
                auto node = *stash[i];
                pos = node.position;
                int value = 3;//桶hash
                file_out.write(reinterpret_cast<char*>(&value), sizeof(value));
                // 写入128位的数值
                file_out.write(reinterpret_cast<char*>(node.content.data()), 16);
        }else{
                pos = 0;
                //写入虚拟值标记
                file_out.write(reinterpret_cast<char*>(&mark), sizeof(mark));
                //写入0bit串
                file_out.write(zerobit,sizeof(zerobit));
            }
              postion_out.write(reinterpret_cast<char*>(&pos), sizeof(pos));//写入位置，0表示虚拟值
    }
    file_out.close();
    postion_out.close();
    std::cout<<cuckoo.get_N();
 
    return 0;
}
